package leetcode;

import java.util.ArrayList;
import java.util.List;

//解决方法 回溯 递归  字典（暴力解题）
public class LeetCode78 {

    //要么选/不选
    //循序遍历
    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        calculation(nums, 0, new ArrayList<>());
        return result;
    }

    private void calculation(int[] nums, int index, List<Integer> lastResult) {
        if (index == nums.length) {
            result.add(lastResult);
            return;
        }
        ArrayList<Integer> list = new ArrayList<>(lastResult);
        list.add(nums[index]);
        calculation(nums, index + 1, lastResult);
        calculation(nums, index + 1, list);
    }
//------------------------------------------------------------------

    //回溯 当前不正确则回溯到上一步
    //每次遍历一种结果 正确添加，错误回溯到上一步
    List<List<Integer>> output = new ArrayList();
    int n, k;

    public void backtrack(int first, ArrayList<Integer> curr, int[] nums) {
        // if the combination is done
        if (curr.size() == k)
            output.add(new ArrayList(curr));

        //n遍历集合
        for (int i = first; i < n; ++i) {
            // add i into the current combination
            curr.add(nums[i]);
            // use next integers to complete the combination
            backtrack(i + 1, curr, nums);
            // backtrack
            //回溯到上一次结果
            curr.remove(curr.size() - 1);
        }
    }

    public List<List<Integer>> subsets1(int[] nums) {
        n = nums.length;
        //k=每个子集的大小
        for (k = 0; k < n + 1; ++k) {
            backtrack(0, new ArrayList<Integer>(), nums);
        }
        return output;
    }
}
